MV(H,<<)
以下の規則によりグラフを生成する.
Definition 5.8 Multiversion Serialization Graph(MVSG)
For a given schedule $ m and a version order $ \ll, the multiversion serialization graph $ MVSG(m, \ll)of $ m then is the conflict graph $ G(m) = (V,E)with the following edges added for each $ r_k(x_j)and $ w_i(x_i)in $ CP(m), where $ k, i,and $ jare pairwise distinct: if $ x_i \ll x_j, then $ (t_i, t_j) \in E, otherwise $ (t_k, t_i) \in E.
WIP. 確かほぼ同じ
Given a log $ L and data item $ x, a version order for $ x is any (nonreflexive) total order over all of the versions of $ x written in $ L. A version order, $ \ll, for $ L is the union of the version orders for all data items. ... Given $ L and a version order $ \ll, the multiversion serialization graph, $ MVSG(L, \ll) is $ SG(L)with the following edges added:
(1) for each $ r_j(x_j)and$ w_i(x_i)in $ L, $ k \ne i, if $ x_i \ll x_jthen include $ T_i \to T_j, else include $ T_k \to T_i.
1. 直接に$ w-rの関係にないReadとWriteのPairをすべて取り出し，
2. Version Order $ \llによって二通りのエッジを追加する．
エッジを張る規則
各文献ごとに，具体的にどのようにエッジを張っているか見る．
https://gyazo.com/09ab64ad26a1da262dc3451e33c8d0ae
https://gyazo.com/adb8970080848754651acaa243a4c028
https://gyazo.com/e465f0339169b5a0f5d6e3521a8b38fb
https://gyazo.com/a725e30b7c4194dea5932b4e16306b26
追加されたエッジは以下:
$ T_0 \to T_4: ... これは規則からはありえないのでは?nikezono.icon
$ T_2 \to T_1: $ r_2(x_0)と$ w_1(x_1)を取り出し，$ x_0 \ll x_1．
$ T_2 \to T_4: ... これもありえない気がするnikezono.icon
$ T_1 \to T_3: $ r_1(z_0)と$ w_3(z_3)を取り出し，$ z_0 \ll z_3．
Read-Only Transactionが，全て最新Versionを読んだ場合，MVにおいてエッジが増えることはないのでは?
$ T_4はそれにあたるトランザクションだが，エッジが増えている．
https://gyazo.com/8ce65ff9f0a643243f66dff62e027ba7
https://gyazo.com/a29d4500c956e000f22dc86755f4263a
SGに対して「追加された」と言われているエッジは以下
1. $ r_1(x_0)と$ w_2(x_2)を取り出し，$ x_0 \ll x_2なので$ T_1 \to T_2
2. $ w_1(y_1)と$ r_4(y_3)を取り出し，$ y_1 \ll y_3なので$ T_1 \to T_3
3. $ r_2(z_0)と$ w_3(z_3)を取り出し，$ z_0 \ll x_3なので$ T_2 \to T_3
「追加」ではないもの(SGにすでにあるEdge)としては，
1. $ w_0(x_0)と$ r_4(x_2)を取り出し，$ x_0 \ll x_2なので$ T_0 \to T_2
なども描ける．